/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/intersection-of-two-arrays-ii
   @Language: C++
   @Datetime: 16-12-07 08:18
   */

class Solution {
public:
	/**
	 * @param nums1 an integer array
	 * @param nums2 an integer array
	 * @return an integer array
	 * Tip: intersection may have duplication
	 */
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
		// Write your code here
		unordered_map<int,int> hm;
		for(int i=nums1.size(); i--; ++hm[nums1[i]]);
		vector<int> v;
		for(int i=nums2.size(); i--;){
			const auto &it = hm.find(nums2[i]);
			if (it==hm.end()) continue;
			v.push_back(it->first);
			if (--it->second==0) hm.erase(it);
		}
		return v;
	}
};
